package cn.yemuysy.code.lingting.core;

import cn.yemuysy.code.lingting.model.MatchResult;
import cn.yemuysy.code.lingting.model.TrieNode;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * AC自动机（Aho-Corasick Algorithm）核心实现
 * 支持多模式串匹配，具有线性时间复杂度
 */
public class AhoCorasickAutomaton {
    
    private static final Logger logger = LoggerFactory.getLogger(AhoCorasickAutomaton.class);
    
    /**
     * Trie树根节点
     */
    private TrieNode root;
    
    /**
     * 是否已构建Fail指针
     */
    private boolean failPointersBuilt;
    
    /**
     * 节点模式（支持字符或音节）
     */
    private boolean syllableMode;
    
    public AhoCorasickAutomaton() {
        this(false);
    }
    
    public AhoCorasickAutomaton(boolean syllableMode) {
        this.root = new TrieNode();
        this.failPointersBuilt = false;
        this.syllableMode = syllableMode;
    }
    
    /**
     * 添加敏感词到Trie树
     * @param word 敏感词
     */
    public void addWord(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }
        
        TrieNode current = root;
        
        if (syllableMode) {
            // 音节模式：按空格分割音节
            String[] syllables = word.trim().split("\\s+");
            for (String syllable : syllables) {
                if (!current.hasChild(syllable)) {
                    current.addChild(syllable, new TrieNode(syllable));
                }
                current = current.getChild(syllable);
            }
        } else {
            // 字符模式：逐字符添加
            for (char character : word.toCharArray()) {
                if (!current.hasChild(character)) {
                    current.addChild(character, new TrieNode(character));
                }
                current = current.getChild(character);
            }
        }
        
        current.setEndOfWord(word);
        
        // 添加新词后需要重新构建Fail指针
        failPointersBuilt = false;
        
        logger.debug("已添加敏感词: {} (模式: {})", word, syllableMode ? "音节" : "字符");
    }
    
    /**
     * 批量添加敏感词
     * @param words 敏感词列表
     */
    public void addWords(Collection<String> words) {
        if (words == null || words.isEmpty()) {
            return;
        }
        
        for (String word : words) {
            addWord(word);
        }
        
        logger.info("批量添加敏感词完成，总计: {} 个", words.size());
    }
    
    /**
     * 构建Fail指针
     * 使用BFS算法构建AC自动机的失效函数
     */
    public void buildFailPointers() {
        if (failPointersBuilt) {
            return;
        }
        
        Queue<TrieNode> queue = new LinkedList<>();
        
        // 第一层节点的Fail指针指向根节点
        for (Object key : root.getChildKeys()) {
            TrieNode child = root.getChild(key);
            child.setFailPointer(root);
            queue.offer(child);
        }
        
        // BFS构建其他层级的Fail指针
        while (!queue.isEmpty()) {
            TrieNode current = queue.poll();
            
            for (Object key : current.getChildKeys()) {
                TrieNode child = current.getChild(key);
                queue.offer(child);
                
                // 寻找child的Fail指针
                TrieNode failNode = current.getFailPointer();
                while (failNode != null && !failNode.hasChild(key)) {
                    failNode = failNode.getFailPointer();
                }
                
                if (failNode != null) {
                    child.setFailPointer(failNode.getChild(key));
                } else {
                    child.setFailPointer(root);
                }
            }
        }
        
        failPointersBuilt = true;
        logger.info("Fail指针构建完成");
    }
    
    /**
     * 搜索文本中的敏感词（字符模式）
     * @param text 要搜索的文本
     * @return 匹配结果列表
     */
    public List<MatchResult> search(String text) {
        if (text == null || text.isEmpty()) {
            return new ArrayList<>();
        }
        
        if (!syllableMode) {
            return searchByCharacter(text);
        } else {
            throw new IllegalStateException("音节模式请使用searchBySyllables方法");
        }
    }
    
    /**
     * 按字符搜索敏感词
     */
    private List<MatchResult> searchByCharacter(String text) {
        if (!failPointersBuilt) {
            buildFailPointers();
        }
        
        List<MatchResult> results = new ArrayList<>();
        TrieNode current = root;
        
        for (int i = 0; i < text.length(); i++) {
            char character = text.charAt(i);
            
            // 如果当前节点没有匹配的子节点，通过Fail指针转移
            while (current != null && !current.hasChild(character)) {
                current = current.getFailPointer();
            }
            
            if (current == null) {
                current = root;
            } else {
                current = current.getChild(character);
                
                // 检查当前节点及其Fail指针链上的所有模式
                TrieNode temp = current;
                while (temp != null) {
                    if (temp.isEndOfWord()) {
                        String matchedWord = temp.getMatchedWord();
                        int startIndex = i - matchedWord.length() + 1;
                        MatchResult result = new MatchResult(matchedWord, startIndex, i, 
                                                           MatchResult.MatchType.NORMAL);
                        results.add(result);
                        
                        logger.debug("匹配到敏感词: {} 位置: {}-{}", matchedWord, startIndex, i);
                    }
                    temp = temp.getFailPointer();
                }
            }
        }
        
        return results;
    }
    
    /**
     * 按音节序列搜索敏感词
     * @param syllables 音节数组
     * @return 匹配结果列表
     */
    public List<MatchResult> searchBySyllables(String[] syllables) {
        if (syllables == null || syllables.length == 0) {
            return new ArrayList<>();
        }
        
        if (!syllableMode) {
            throw new IllegalStateException("字符模式请使用search方法");
        }
        
        if (!failPointersBuilt) {
            buildFailPointers();
        }
        
        List<MatchResult> results = new ArrayList<>();
        TrieNode current = root;
        
        for (int i = 0; i < syllables.length; i++) {
            String syllable = syllables[i];
            
            // 如果当前节点没有匹配的子节点，通过Fail指针转移
            while (current != null && !current.hasChild(syllable)) {
                current = current.getFailPointer();
            }
            
            if (current == null) {
                current = root;
            } else {
                current = current.getChild(syllable);
                
                // 检查当前节点及其Fail指针链上的所有模式
                TrieNode temp = current;
                while (temp != null) {
                    if (temp.isEndOfWord()) {
                        String matchedWord = temp.getMatchedWord();
                        String[] matchedSyllables = matchedWord.trim().split("\\s+");
                        int startIndex = i - matchedSyllables.length + 1;
                        MatchResult result = new MatchResult(matchedWord, startIndex, i, 
                                                           MatchResult.MatchType.PINYIN);
                        results.add(result);
                        
                        logger.debug("匹配到拼音敏感词: {} 位置: {}-{}", matchedWord, startIndex, i);
                    }
                    temp = temp.getFailPointer();
                }
            }
        }
        
        return results;
    }
    
    /**
     * 检查是否包含敏感词
     * @param text 要检查的文本
     * @return true如果包含敏感词
     */
    public boolean containsSensitiveWord(String text) {
        List<MatchResult> results = search(text);
        return !results.isEmpty();
    }
    
    /**
     * 获取敏感词数量统计
     * @return 当前AC自动机中的敏感词数量
     */
    public int getWordCount() {
        return countWords(root);
    }
    
    /**
     * 递归统计敏感词数量
     */
    private int countWords(TrieNode node) {
        int count = 0;
        if (node.isEndOfWord()) {
            count++;
        }
        
        for (Object key : node.getChildKeys()) {
            count += countWords(node.getChild(key));
        }
        
        return count;
    }
    
    /**
     * 清空AC自动机
     */
    public void clear() {
        this.root = new TrieNode();
        this.failPointersBuilt = false;
        logger.info("AC自动机已清空");
    }
    
    /**
     * 获取根节点（用于调试）
     */
    public TrieNode getRoot() {
        return root;
    }
    
    /**
     * 检查是否为音节模式
     */
    public boolean isSyllableMode() {
        return syllableMode;
    }
    
    /**
     * 检查Fail指针是否已构建
     */
    public boolean isFailPointersBuilt() {
        return failPointersBuilt;
    }
    
    @Override
    public String toString() {
        return "AhoCorasickAutomaton{" +
                "wordCount=" + getWordCount() +
                ", syllableMode=" + syllableMode +
                ", failPointersBuilt=" + failPointersBuilt +
                '}';
    }
} 